package com.freedy.dataStructure.linkedList;

import java.util.Comparator;

/**
 * 单表的实现
 * @author Freedy
 * @date 2021/3/14 14:16
 */
public class SingleLinkedList<T> {
    //先初始化头节点,头节点不能变动
    private final Node<T> head;

    SingleLinkedList() {
        head = new Node<>();
    }

    public Node<T> getHead() {
        return head;
    }

    public void add(T data) {
        Node<T> node = new Node<>();
        node.setData(data);
        addNode(node);
    }

    /**
     * 带索引的添加 相当于插入
     * @param index
     * @param data
     */
    public void add(int index, T data) {
        Node<T> node = new Node<>();
        node.setData(data);
        setNode(index, node);
    }


    public T get(int index) {
        Node<T> node = getNode(index);
        return node.getData();
    }

    /**
     * @param index 索引
     */
    public void remove(int index) {
        //获取前置节点
        Node<T> pre = getNode(index - 1);
        Node<T> node = getNode(index);
        pre.setNext(node.getNext());
    }

    public void revers(){
        if (size()==0) throw new RuntimeException("链表为空");
        Node<T> preNode = head.getNext();
        Node<T> node = preNode.getNext();
        preNode.setNext(null);
        while (node!=null){
            Node<T> temp = node.getNext();
            node.setNext(preNode);
            preNode=node;
            node=temp;
        }
        head.setNext(preNode);
    }


    public void printRevers(Node<T> head){
        if (head!=null){
            printRevers(head.getNext());
            if (head.data!=null){
                System.out.print(head.data+" ");
            }
        }
    }


    /**
     * @return 链表大小
     */
    public int size() {
        int size = 0;
        Node<T> temp = head.getNext();
        while (temp != null) {
            size++;
            temp = temp.getNext();
        }
        return size;
    }

    /**
     * 冒泡法排序
     * @param c
     */
    @SuppressWarnings("unchecked")
    public void sort(Comparator<T> c) {
        Node<T> node = head.getNext();
        Object[] sort=new Object[size()];
        int num=0;
        while (node!=null){
            sort[num]=node.getData();
            node=node.getNext();
            num++;
        }
        for (int i = sort.length-1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (c.compare((T)sort[j],(T)sort[j+1])>0){
                    Object temp;
                    temp=sort[j];
                    sort[j]=sort[j+1];
                    sort[j+1]=temp;
                }
            }
        }
        head.setNext(null);
        for (Object o : sort) {
            add((T) o);
        }
    }

    /**
     * ==================private====================
     * 链表添加值
     *
     * @param node
     */
    private void addNode(Node<T> node) {
        getNode(size() - 1).setNext(node);
    }

    /**
     * 给链表设置值
     *
     * @param index 索引
     * @param node  节点
     */
    private void setNode(int index, Node<T> node) {
        Node<T> temp = getNode(index - 1);
        //这里拿到的temp是index的前一个节点
        Node<T> mark;
        mark = temp.getNext();
        temp.setNext(node);
        node.setNext(mark);
    }

    /**
     * 获取链表
     * index为-1时获取的是头head
     *
     * @param index 索引
     * @return 节点
     */
    private Node<T> getNode(int index) {
        int count = -1;
        Node<T> temp = head;
        boolean isOver = true;
        while (temp != null) {
            if (index == count) {
                isOver = false;
                break;
            }
            count++;
            temp = temp.getNext();
        }
        if (isOver) {
            throw new RuntimeException("链表超界 数组大小:"+size()+" index:"+index);
        }
        return temp;
    }

    /**
     * 遍历整个列表
     */
    @Override
    public String toString() {
        if (head.getNext() == null) {
            return "[]";
        }
        Node<T> temp = head.getNext();
        StringBuilder stringBuffer = new StringBuilder();
        stringBuffer.append("[");
        while (temp != null) {
            stringBuffer.append(temp.getData().toString()).append(",");
            temp = temp.getNext();  //将temp后移
        }
        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
        stringBuffer.append("]");
        return stringBuffer.toString();
    }

    /**
     * 定义一个node类
     *
     * @param <T>
     */
    private static class Node<T> {
        private T data;
        private Node<T> next;

        private T getData() {
            return data;
        }

        private void setData(T data) {
            this.data = data;
        }

        private Node<T> getNext() {
            return next;
        }

        private void setNext(Node<T> next) {
            this.next = next;
        }
    }

}
